
// https://leetcode.cn/problems/path-sum/
public class TargetSum {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public boolean hasPathSum(TreeNode root, int targetSum) {
            if(root == null) return false;
            return search(root,targetSum-root.val);

        }

        private boolean search(TreeNode node,int sum)
        {
            if(sum == 0 && node.left == null && node.right == null){
                return true;
            }
            if(node.left != null){
                if(search(node.left,sum - node.left.val)) return true;
            }
            if(node.right != null)
            {
                if(search(node.right,sum-node.right.val)) return true;
            }
            return false;
        }


    }
}
